Sentence screen fitting

Time: O(R+NxC); Space: O(N); medium

Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Constraints:

  • A word cannot be split into two lines.

  • The order of words in the sentence must remain unchanged.

  • Two consecutive words in a line must be separated by a single space.

  • Total words in the sentence won’t exceed 100.

  • Length of each word is greater than 0 and won’t exceed 10.

  • 1 <= rows, cols <= 20,000.

Example 1:

Input: sentence = [“I”, “had”, “apple”, “pie”], rows = 4, cols = 5

Output: 1

Explanation:

I-had
apple
pie-I
had--

  • The character ‘-’ signifies an empty space on the screen.

Example 2:

Input: sentence = [“hello”, “world”], rows = 2, cols = 8

Output: 1

Explanation:

hello---
world---

  • The character ‘-’ signifies an empty space on the screen.

Example 3:

Input: sentence = [“a”, “bcd”, “e”], rows = 3, cols = 6

Output: 2

Explanation:

a-bcd-
e-a---
bcd-e-

  • The character ‘-’ signifies an empty space on the screen.

[1]:

class Solution1(object):
    """
    Time: O(R+N*C)
    Space: O(N)
    """
    def wordsTyping(self, sentence, rows, cols):
        """
        :type sentence: List[str]
        :type rows: int
        :type cols: int
        :rtype: int
        """
        def words_fit(sentence, start, cols):
            if len(sentence[start]) > cols:
                return 0

            s, count = len(sentence[start]), 1
            i = (start + 1) % len(sentence)
            while s + 1 + len(sentence[i]) <= cols:
                s += 1 + len(sentence[i])
                count += 1
                i = (i + 1) % len(sentence)
            return count

        wc = [0] * len(sentence)
        for i in range(len(sentence)):
            wc[i] = words_fit(sentence, i, cols)

        words, start = 0, 0
        for i in range(rows):
            words += wc[start]
            start = (start + wc[start]) % len(sentence)

        return words // len(sentence)

[2]:

s = Solution1()

sentence = ["I", "had", "apple", "pie"]
rows = 4
cols = 5
assert s.wordsTyping(sentence, rows, cols) == 1

sentence = ["hello", "world"]
rows = 2
cols = 8
assert s.wordsTyping(sentence, rows, cols) == 1

sentence = ["a", "bcd", "e"]
rows = 3
cols = 6
assert s.wordsTyping(sentence, rows, cols) == 2